package com.watson.onebox.algorithm.dijkstra;

import java.util.Arrays;

public class KruskalCase {
    /*
     * 克鲁斯卡尔(Kruskal)算法求最小生成树:
     * 克鲁斯卡尔(Kruskal)算法，是用来求加权连通图的最小生成树的算法。
     * (1)基本思想：按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路
     * (2)具体做法：首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止
     * */
    //定义若干属性
    //1.定义边的个数
    private int edgeNum;
    //2.定义顶点的数组:用来存储从顶点'A' 到 'G'的数组元素
    private char[] vertexs;
    //3.使用INF表示两个顶点之间是无法连通的:即两个顶点的边的长度取Integer的最大值
//    private static final int INF = Integer.MAX_VALUE;
    private static final int INF = -1;
    //4.定义邻接矩阵
    private int[][] matrix;

    //定义构造器
    public KruskalCase(char[] vertexArr,int[][] matrixArr) {
        int vlen = vertexArr.length;//初始化顶点数和边的个数
        //初始化顶点:利用拷贝的方法:即初始化vertexs
        this.vertexs = new char[vlen];
        for (int i = 0; i < vertexs.length; i++) {
            this.vertexs[i] = vertexArr[i];//将传入的顶点数据保存到KruskalCase的vertexs的顶点数组中
        }
        //初始化边:也使用复制拷贝的方式:即初始化matrix
        this.matrix = new int[vlen][vlen];//行和列均为vlen长度
        for (int i = 0; i < vlen; i++) {
            for (int j = 0; j < vlen; j++) {
                this.matrix[i][j] = matrixArr[i][j];
            }
        }
        //统计边的个数:即初始化edgeNum
        for (int i = 0; i < vlen; i++) {
            for (int j = i + 1; j < vlen; j++) {
                if (this.matrix[i][j] != INF) {
                    edgeNum++;
                }
            }
        }
    }

    public static void main(String[] args) {
        char[] vertexsArr = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        //克鲁斯卡尔算法的邻接矩阵
        int[][] matrixArr = {
                        /*A*//*B*//*C*//*D*//*E*//*F*//*G*/
                /*A*/ {   0,  12, INF, INF, INF,  16,  14},
                /*B*/ {  12,   0,  10, INF, INF,   7, INF},
                /*C*/ { INF,  10,   0,   3,   5,   6, INF},
                /*D*/ { INF, INF,   3,   0,   4, INF, INF},
                /*E*/ { INF, INF,   5,   4,   0,   2,   8},
                /*F*/ {  16,   7,   6, INF,   2,   0,   9},
                /*G*/ {  14, INF, INF, INF,   8,   9,   0}};
        //创建KruskalCase实例
        KruskalCase kruskalCase = new KruskalCase(vertexsArr,matrixArr);
        //进行最小生成树的构建
        kruskalCase.print();//图的邻接矩阵的输出打印
        kruskalCase.kruskal();//通过Kruskal算法进行最小生成树的构建

    }

    //Kruskal算法方法
    public void kruskal() {
        //创建索引:表示最后数组的缩影
        int index = 0;
        //ends下标是边起始点的下标，值是边终点的下标
        int[] ends = new int[edgeNum];//用于保存"已有最小生成树" 中的每个顶点在最小生成树中的终点
        //创建结果数组,保存最后得到的最小生成树结果
        EdgeData[] minTree = new EdgeData[edgeNum];
        //1.首先获取图中所有边的对象的集合
        EdgeData[] edgeArr = getEdgeArr();
        System.out.println("图的边的集合=\\n" + Arrays.toString(edgeArr) + " 共有边(条数):"+ edgeArr.length);
        //2.对这些边进行排序处理:按从小到大排序
        sortEdge(edgeArr);
        //输出排序后的边的集合:
        System.out.println("排序以后图的边的集合=\\n" + Arrays.toString(edgeArr) + " 共有边(条数):"+ edgeArr.length);
        //3.遍历edgeArr数组:将边添加到最小生成树中
        //因为已经进行了排序:所以我们依次添加即可
        //只要注意每次添加时判断是否形成回路,若形成回路,则放弃该条边
        for (int i = 0; i < edgeNum; i++) {
            //首先获取到边的第一个顶点
            int start = getPosition(edgeArr[i].start);
            //再获取到边的第二个顶点
            int end = getPosition(edgeArr[i].end);

            //分别获取两个顶点的终点
            int dest1 = getEnd(ends,start);
            int dest2 = getEnd(ends,end);
            //判断是否构成回路:也就是这两个顶点的终点是否相同
            if (dest1 != dest2) {   //此时没有构成回路
                //第一次E和F,通过getEnd方法:dest1 = 4;dest2 = 5,则将ends[4] = 5:即将E的终点设置为F
                ends[dest1] = dest2;//将此时dest1在"已有的最小生成树"中的终点设置为dest2
                System.out.println("访问到了节点：{" + vertexs[start] + "," + vertexs[end] + "}，权值：" + matrix[start][end]);
                //注意:我们无需对dest2的终点进行设置
                //并将此时有效的边加入到minTree数组中
                minTree[index++] = edgeArr[i];
            }
        }
        //最终通过for循环的遍历添加处理得到最小生成树:
        System.out.println("得到的最小生成树为:");
        for (int i = 0; i < index; i++) {//将打印的上界设为index:即最终最小生成树的边的个数
            System.out.println(minTree[i]);
        }
    }

    //定义方法1:打印邻接矩阵
    public void print() {
        System.out.println("图的邻接矩阵为:");
        for (int i = 0; i < vertexs.length; i++) {
            for (int j = 0; j < vertexs.length; j++) {
                System.out.printf("%12d",matrix[i][j]);//将邻接矩阵数据输出打印:格式化
            }
            System.out.println();//换行处理
        }
    }

    //定义方法2:对边进行排序处理:这里采用较为简单的冒泡排序法
    private void sortEdge(EdgeData[] edgeArr) {//edgeArr存储每个有效边的对象的集合
        for (int i = 0; i < edgeArr.length - 1; i++) {//冒泡排序排序次数:edgeArr.length - 1次
            for (int j = 0; j < edgeArr.length - 1 - i; j++) {
                if (edgeArr[j].weight > edgeArr[j + 1].weight) {
                    //进行交换,则按照从小到大排序
                    EdgeData temp = edgeArr[j];
                    edgeArr[j] = edgeArr[j + 1];
                    edgeArr[j + 1] = temp;
                }
            }
        }
    }

    //定义方法3:根据指定的顶点的值返回其对应的下标
    private int getPosition(char vertex) {
        for (int i = 0; i < vertexs.length; i++) {
            if (vertexs[i] == vertex) {
                return i;
            }
        }
        //找不到则返回-1
        return -1;
    }

    //定义方法4:获取图中的边:将其放到EdgeData[] 数组中,后面需要进行遍历
    //通过邻接矩阵martrix邻接矩阵得到
    //得到的结果EdgeData[] 形式 [['A','B', 12], ['B','F',7], .....]
    private EdgeData[] getEdgeArr() {
        int index = 0;
        EdgeData[] edgeArr = new EdgeData[edgeNum];//数组大小为当前给出的图的所有的边的个数
        for (int i = 0; i < vertexs.length; i++) {
            for (int j = i+1; j < vertexs.length; j++) {
                if (matrix[i][j] != INF) {
                    //说明两个顶点存在边
                    edgeArr[index++] = new EdgeData(vertexs[i],vertexs[j],matrix[i][j]);
                }
            }
        }
        return edgeArr;//将得到的所有的边的对象的数组返回
    }

    //定义方法5:获取下标为i的顶点的终点:用来后面判断两个顶点的终点是否相同
    private int getEnd(int[] ends,int i) {
        //ends:该数组用来记录各个顶点对应的终点是哪一个:刚开始均为0
        //i:即表示传入的查询终点的顶点的下标
        //很巧妙的计算终点
        while (ends[i] != 0) {
            i = ends[i];//若当前i的终点不为0,则将其赋值给i
        }
        return i;//若当前i的终点为0,即i的顶点刚加入,则自己即为其顶点
    }

    //定义一个类EdgeData:表示一条边:里面保存一条边的两个顶点以及这条边的长度(即权值)
    class EdgeData {
        //定义边的属性
        public char start;//边的一个顶点
        public char end;///边的另一个顶点
        public int weight;//边的权值

        public EdgeData(char start, char end, int weight) {
            this.start = start;
            this.end = end;
            this.weight = weight;
        }

        @Override
        public String toString() {
            return "EdgeData [<" + start + "," + end + "> weight=" + weight + ']' +'\n';
        }
    }
}
